// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-21 12:16
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.topKFrequent;

import java.util.*;

public class topKFrequent_ {
    // 前K个高频单词
    // 获取给定列表中的前K个高频单词，如果频率相同则按字典序进行输出
    // 使用map对单词出现次数进行存储，并且自定义比较器实现结果输出
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();

        for (String word : words) {
            Integer val = map.getOrDefault(word, 0);
            map.put(word, ++val);
        }
        int wordNum = map.size();
        List<intString> wordFrequent = new ArrayList<>();
        ArrayList<String> res = new ArrayList<>();
        for (String key : map.keySet()) {
            wordFrequent.add(new intString(map.get(key), key));
        }
        Collections.sort(wordFrequent);
        Iterator<intString> iterator = wordFrequent.iterator();
        while (iterator.hasNext()) {
            intString next = iterator.next();
            res.add(next.words);
            k--;
            if (k <= 0) {
                break;
            }
        }
        return res;
    }

    public class intString implements Comparable<intString> {
        public int time;
        public String words;

        public intString(int time, String words) {
            super();
            this.time = time;
            this.words = words;
        }

        public int getTime() {
            return time;
        }

        public String getWords() {
            return words;
        }

        @Override
        public int compareTo(intString o) {
            return this.time == o.time ? (
                    this.words.compareTo(o.words)) : this.time - o.time;
        }
    }
}
